package com.queue.test;

import java.util.LinkedList;
import java.util.Random;

public class GetMaxValue {

	public static int[] getCurrentWindowMaxValue(int[] arr, int w) {
		if (arr == null || w < 1 || arr.length < w) {
			return null;
		}
		LinkedList<Integer> qmax = new LinkedList<Integer>();
		//计算最大的长度
		int[] res = new int[arr.length - w + 1];
		int index = 0;
		for (int i = 0; i < arr.length; i++) {
			while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]) {//如果队列不为空，并且队列中最后的元素小于当前的元素删除最后的元素
				qmax.pollLast();
			}
			qmax.addLast(i);//添加数组的元素到最后的位置 1):i-w：计算下一个时间该窗口的最后一个可以计算下标 2):qmax.peekFirst():获取
			if (qmax.peekFirst() == i - w) {// arr[3,4,5]，而此时qmax下标为2，当前下标已经过期，则弹出  如果 队列的第一个下标，标识队列第一个小标已经过期，需要弹出
				qmax.pollFirst();
			}
			if (i >= w - 1) {// 如i=3，w=3，此时窗口下标应为[1,2,3]，index为0，故此时index加1，即窗口右移
				res[index++] = arr[qmax.peekFirst()];// 当前窗口的最大值，即窗口右移一位后的首部
			}
		}
		return res;
	}

	// for test
	public static void printArray(int[] arr) {
		for (int i = 0; i != arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	public static void printEach(int[] arr) {
		System.out.println("当前数组为：");
		for (int j = 0; j < arr.length; j++) {
			System.out.print(arr[j] + ",");
		}
		System.out.println();
	}

	public static void main(String[] args) {
//		int[] arr_test = new int[10];
//		Random ran = new Random();
//		for (int i = 0; i < 10; i++) {
//			int random = ran.nextInt(100);
//			arr_test[i] = random;
//		}
//		printEach(arr_test);
//		int w = 3;
//		printArray(getCurrentWindowMaxValue(arr_test, w));
		
	}

}
